1659B - Bit Flipping - CodeForces Solution

import math
import random
import sys




p2D = lambda x: print(*x, sep="\n")


def II(): return int(sys.stdin.buffer.readline())


def MI(): return map(int, sys.stdin.buffer.readline().split())


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def BI(): return sys.stdin.buffer.readline().rstrip()


def SI(): return sys.stdin.buffer.readline().rstrip().decode()


def li(): return [int(i) for i in input().split()]


def lli(rows): return [li() for _ in range(rows)]


def si(): return input()


def ii(): return int(input())


def ins(): return input().split()



def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1


def binary_search(n, a):
    l = len(a)
    low = 0
    high = l - 1
    while high >= low:
        mid = (high + low) // 2
        if a[mid] == n:
            return mid
        elif a[mid] > n:
            high = mid - 1
        else:
            low = mid + 1
    return -1





def gcd(a,b):
    if b==0:
        x = 1
        y = 0
        return x, y, a
    x, y, g = gcd(b, a%b)
    return y, x- (a//b)*y, g

def solve():
    n, k = LI()
    s = SI()
    cnts = [0] * n
    p = k%2
    for i in range(n):
        if s[i] == str(p) and k:
            cnts[i] += 1
            k-=1
    cnts[-1] += k
    return ''.join([str(((cnts[i] + p) % 2) ^ int(s[i])) for i in range(n)])+ '\n'+' '.join(list(map(str, cnts)))


def main():
            for _ in range(II()):
        sys.stdout.write(str(solve()) + "\n")
                                    
            



if __name__ == "__main__":
    main()